package org.jkuang.qstar.commons.util;

import java.util.Arrays;
/**
 * 
 * @author jkuang 2012年11月17日
 *
 */
public class BTreeBlock {

	protected volatile int size;
	protected volatile long[] keys;
	protected volatile int[] docKeys;

	public int get(long key) {
		int index = indexOf(key, SerarChType._index);
		if (index >= 0) {
			return docKeys[index];
		} else {
			return -1;
		}
	}

	/**
	 * 插入元素
	 *
	 * @param node
	 * @return
	 */
	protected int insert(long key, int doc) {
		if (size == 0 || compare(key, keys[size - 1]) > 0) {
			ensureKeyCapacity(size + 1); // Increments modCount!!
			ensureDataCapacity(size + 1);
			this.docKeys[size] = doc;
			keys[size++] = key;
			return size - 1;
		} else {
			int index = indexOf(key, SerarChType._insert);
			if (index >= 0) {
				// 如果元素已经存在
				ensureKeyCapacity(size + 1);
				ensureDataCapacity(size + 1);
				System.arraycopy(keys, index, keys, index + 1, size - index);
				System.arraycopy(docKeys, index, docKeys, index + 1, size - index);
				this.keys[index] = key;
				this.docKeys[index] = doc;
				size++;
			}
			return index;
		}
	}

	/**
	 * 删除元素
	 *
	 * @param node
	 * @return
	 */
	protected int delete(long key) {
		int index = indexOf(key, SerarChType._index);
		if (index < 0) {
			return index;
		} else {
			if (size - index - 1 > 0) {
				long[] newNodes = new long[size - 1];
				int[] newDocs = new int[size - 1];
				System.arraycopy(keys, 0, newNodes, 0, index);
				System.arraycopy(keys, index + 1, newNodes, index, size - index - 1);

				System.arraycopy(docKeys, 0, newDocs, 0, index);
				System.arraycopy(docKeys, index + 1, newDocs, index, size - index - 1);
				this.docKeys = newDocs;
				this.keys = newNodes;
			}
			size--;
			return index;
		}

	}

	int indexOf(long key, SerarChType type) {
		int fromIndex = 0;
		int toIndex = this.size - 1;
		while (fromIndex <= toIndex) {
			int mid = (fromIndex + toIndex) >> 1;
			int cmp = this.compare(keys[mid], key);
			if (cmp < 0)
				fromIndex = mid + 1;
			else if (cmp > 0)
				toIndex = mid - 1;
			else
				return type == SerarChType._insert ? -(mid + 1) : mid; // key
																		// found
		}
		switch (type) {
		case _insert:
		case _ceil:
			return fromIndex;
		case _index:
			return -(fromIndex + 1);
		default:
			return toIndex;
		}
	}

	public int size() {
		return size;
	}

	public int size(int begin, int end) {
		int _s_index = 0;
		int _e_index = this.size - 1;
		if (compare(begin, keys[0]) > 0) {
			_s_index = indexOf(begin, SerarChType._ceil);
		}
		if (compare(end, keys[size - 1]) < 0) {
			_e_index = indexOf(end, SerarChType._floor);
		}
		return _e_index - _s_index + 1;
	}

	/**
	 * 该区间的范围是否包含指定元素
	 *
	 * @param node
	 * @return
	 */
	public int rangeContains(long key) {
		// 在区间段的左边
		if (compare(keys[size - 1], key) < 0) {
			return -1;
		} else if (compare(keys[0], key) > 0) {
			return 1;
		} else {
			return 0;
		}
	}

	/**
	 * 将Block分裂成两个块
	 *
	 * @return
	 */
	public BTreeBlock[] splitToTwo() {
		BTreeBlock[] blocks = new BTreeBlock[2];
		int mid = this.size >> 1;
		blocks[0] = new BTreeBlock();
		blocks[0].keys = Arrays.copyOfRange(keys, 0, mid);
		blocks[0].docKeys = Arrays.copyOfRange(docKeys, 0, mid);
		blocks[0].size = mid;

		blocks[1] = new BTreeBlock();
		blocks[1].keys = Arrays.copyOfRange(keys, mid, this.size);
		blocks[1].docKeys = Arrays.copyOfRange(docKeys, mid, this.size);
		blocks[1].size = this.size - mid;
		return blocks;
	}

	/**
	 * 
	 * @param key1
	 * @param key2
	 * @return
	 */
	protected int compare(long key1, long key2) {
		if (key1 > key2) {
			return 1;
		} else if (key1 < key2) {
			return -1;
		} else {
			return 0;
		}
	}

	/**
	 * 给元素扩容
	 *
	 * @param minCapacity
	 */
	public void ensureKeyCapacity(int minCapacity) {
		int oldCapacity = keys.length;
		if (minCapacity > oldCapacity) {
			int newCapacity = Math.min(oldCapacity >>> 1 + 1, 256) + oldCapacity;
			if (newCapacity < minCapacity) {
				newCapacity = minCapacity;
			}
			keys = Arrays.copyOf(keys, newCapacity);
		}
	}

	public void ensureDataCapacity(int minCapacity) {
		int oldCapacity = docKeys.length;
		if (minCapacity > oldCapacity) {
			int newCapacity = Math.min(oldCapacity >>> 1 + 1, 256) + oldCapacity;
			if (newCapacity < minCapacity) {
				newCapacity = minCapacity;
			}
			docKeys = Arrays.copyOf(docKeys, newCapacity);
		}
	}

}

enum SerarChType {
	_insert, _ceil, _index, _floor;
}
